import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 输出一个串的所有可能字符组合，例如输入“abcd“，
 输出a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd
 输入串可能会有重复字符，例如输入”abcc“，输出a,b,c,ab,bc,ac,cc,abc,acc,bcc
 */
public class VantString {
    static Set<String> all = new HashSet<>();

    public static Set<String> getPermutation(String str) {

//创建 set 集合以避免重复排列

        Set<String> permutations = new HashSet<>();

//检查字符串是否为空

        if (str == null) {

            return null;

        } else if (str.length() == 0) {

//递归的终止条件
            permutations.add("");
            return permutations;

        }

//得到第一个字符

        char first = str.charAt(0);

//获取剩余的子字符串

        String sub = str.substring(1);

//递归调用getPersertion()

        Set<String> words = getPermutation(sub);

//遍历 words

        for (String strNew : words) {

            for (int i = 0; i <= strNew.length(); i++) {

//将排列插入到set集合中

                permutations.add(strNew.substring(0, i) + first + strNew.substring(i));

            }

        }

        return permutations;

    }

    static void progress(String str) {
        //List<boolean> flags=new ArrayList<>();
        String temp = "";
        //循环2的长度次方
        for (int i = 1; i < (1 << str.length()); i++) {
            //转换成二进制，位数和str长度相同，少于则补0
            String falgs = Integer.toBinaryString(i);
            for (int t = falgs.length(); t < str.length(); t++)
                falgs = "0" + falgs;

            int j = 0;
            for (int k = 0; k < falgs.length(); k++) {
                //把二进制上所有为1的字符，组合成一个新的字符串
                if (falgs.charAt(k) == '1') {
                    //temp+=str.charAt(str.length()-1-k);
                    temp += str.charAt(k);
                }
            }
            //所有temp中字符串的所有组合，比如，abc有：abc,acb,cba等
            //System.out.println(temp);
            Set<String> permutation = getPermutation(temp);
            //System.out.println(permutation);
            all.addAll(permutation);

//            //加入Set
//            all.add(temp);
//            //颠倒后再加入
//            temp=new  StringBuilder(temp).reverse().toString();
//            if(!all.contains(temp))
//                all.add(temp);
            temp = "";
        }
        for (String t : all)
            System.out.println(t);
    }

    public static void main(String[] args) {
        String str = "AABC";
//        char[] chars = str.toCharArray();
//        List<Character> list = new ArrayList<>();
//        for (char c : chars)
//            list.add(c);

        progress(str);
    }
}
